package niuke;

/**
 * 根据前序遍历和中序遍历重建二叉树
 */
public class Solution3 {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return dfs(0,0,vin.length-1, pre,vin);
    }
    public TreeNode dfs(int ps, int is, int end, int []pre, int []vin){
        if( ps > pre.length -1 || is > end) return null;
        TreeNode root = new TreeNode( pre[ps]);
        int index = 0;
        for(int i=0; i<=end; i++){
            if( pre[ps] == vin[i]){
                index = i;
                break;
            }
        }
        int k = index - is +1;
        root.left = dfs( ps+1, is, index-1, pre,vin);
        root.right = dfs( ps+k, index+1, end, pre, vin);
        return root;
    }
}